﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
#include <utility> //pair头文件
using namespace std;

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        vector<vector<int>> vv;
        // 处理边界情况
        if (root == nullptr) return vv;
        queue<Node*> q;
        // 让根节点入队列
        q.push(root);

        while (!q.empty())
        {
            // 先计算当前队列的大小
            int size = q.size();
            vector<int> tmp;
            // 循环当前层
            for (int i = 0; i < size; i++)
            {
                Node* x = q.front();
                q.pop();
                tmp.push_back(x->val);
                // 遍历所有的孩子节点，并让其入队列
                for (auto child : x->children)
                    q.push(child);
            }
            vv.push_back(tmp);
        }
        return vv;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};
// ⼆叉树的锯⻮形 层序遍历
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> vv;
        if (root == nullptr) return vv;

        queue<TreeNode*> q;
        q.push(root);

        int level = 1;

        while (!q.empty())
        {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++)
            {
                TreeNode* x = q.front();
                q.pop();
                tmp.push_back(x->val);

                if (x->left)
                    q.push(x->left);
                if (x->right)
                    q.push(x->right);
            }
            // 判断是否逆序，偶数层才逆序
            if (level % 2 == 0)
                reverse(tmp.begin(), tmp.end());
            vv.push_back(tmp);
            level++;
        }
        return vv;
    }
};

// ⼆叉树的最⼤宽度
//class Solution {
//public:
//    int widthOfBinaryTree(TreeNode* root)
//    {
//        vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列
//        q.push_back({ root, 1 });
//        unsigned int ret = 0;
//        while (q.size())
//        {
//            // 先更新这⼀层的宽度
//            auto& [x1, y1] = q[0];
//            auto& [x2, y2] = q.back();
//            ret = max(ret, y2 - y1 + 1);
//
//            // 让下⼀层进队
//            vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列
//            for (auto& [x, y] : q)
//            {
//                if (x->left) tmp.push_back({ x->left, y * 2 });
//                if (x->right)    tmp.push_back({ x->right, y * 2 + 1 });
//            }
//            q = tmp;
//        }
//        return ret;
//    }
//};

// 在每个树⾏中找最⼤值  层序遍历
class Solution {
public:
    vector<int> largestValues(TreeNode* root)
    {
        vector<int> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);

        // 层序遍历
        while (!q.empty())
        {
            // 因为数值有可能为负数，所以将Max初始化为最小值
            int size = q.size(), Max = INT_MIN;

            // 遍历每一层，找最大值
            for (int i = 0; i < size; i++)
            {
                TreeNode* cur = q.front();
                Max = max(Max, cur->val);
                q.pop();

                if (cur->left)   q.push(cur->left);
                if (cur->right)  q.push(cur->right);
            }
            // 将每层的最大值push到ret中
            ret.push_back(Max);
        }
        return ret;
    }
};

// 优先级队列
class Solution {
public:
    int lastStoneWeight(vector<int>& stones)
    {
        // 创建一个大根堆
        priority_queue<int> q;

        // 将stones中的数据丢入q中
        for (auto e : stones)    q.push(e);
        // 模拟
        while (q.size() > 1)
        {
            int x = q.top();    q.pop();
            int y = q.top();    q.pop();
            if (x == y);
            else q.push(x - y);
        }
        return  q.empty() ? 0 : q.top();
    }
};
// 优先级队列 - 练习
class KthLargest {
public:
    //  创建一个小根堆
    priority_queue<int, vector<int>, greater<int>> q;
    int _k;
    KthLargest(int k, vector<int>& nums)
        :_k(k)
    {
        for (auto& e : nums)
            add(e);
    }

    int add(int val)
    {
        q.push(val);
        if (q.size() > _k)   q.pop();
        return q.top();
    }
};
#include <unordered_map>
// 前 K 个⾼频单词  优先级队列实现
class Solution {
public:
    struct Compare
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
        {
            return x.second > y.second || (x.first < y.first && x.second == y.second);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        // 利用哈希表统计次数
        unordered_map<string, int> hash;
        for (auto& e : words)
            hash[e]++;
        // 创建小根堆
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> q;
        for (auto& e : hash)
        {
            // 将哈希表中的数据入队列
            q.push(e);
            // 当队列中的元素个数大于k个时，出队列， 最后剩余的元素就是我们需要的元素
            if (q.size() > k)
                q.pop();
        }

        vector<string> v(k);
        for (int i = k - 1; i >= 0; i--)
        {
            v[i] = q.top().first;
            q.pop();
        }
        return v;
    }
};
#include <map>
// 排序实现
class Solution {
public:
    struct Compare
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
        {
            return x.second > y.second || (x.second == y.second) && x.first < y.first;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> CountMap;
        for (auto& e : words)
        {
            CountMap[e]++;// 去重，并按e.first进行排序
        }

        vector<pair<string, int>> v(CountMap.begin(), CountMap.end());
        //stable_sort(v.begin(),v.end(),Compare());// 按second排序
        sort(v.begin(), v.end(), Compare());

        vector<string> strV;
        for (int i = 0; i < k; i++)
        {
            strV.push_back(v[i].first);
        }
        return strV;
    }
};
// 搜索二维矩阵ii
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        // 从右上角开始搜索
        int row = 0, col = matrix[0].size() - 1;
        for (; row < matrix.size() && col >= 0;)
        {
            // 若目标值大于当前值，则让行数++
            if (target > matrix[row][col])
                row++;
            // 若目标值小于当前值，则让列数--
            else if (target < matrix[row][col])
                col--;
            // 两值相等即返回
            else    return true;
        }
        return false;
    }
};
// 数据流的中位数 堆
class MedianFinder
{
    priority_queue<int> left; // ⼤根堆
    priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:
    MedianFinder()
    {}
    void addNum(int num)
    {
        // 分类讨论即可
        if (left.size() == right.size()) // 左右两个堆的元素个数相同
        {
            if (left.empty() || num <= left.top()) // 放 left ⾥⾯
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if (num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }
    }
    double findMedian()
    {
        if (left.size() == right.size()) return (left.top() + right.top()) /
            2.0;
        else return left.top();
    }
};
// 双指针
class Solution {
public:
    vector<int> subSort(vector<int>& array)
    {
        vector<int> ret{ -1, -1 };
        int len = array.size();
        if (len <= 1)    return ret;

        int max = INT_MAX, min = INT_MIN;
        // 找到left
        for (int i = len - 1; i >= 0; i--)
        {
            if (array[i] > max)  ret[0] = i;
            else    max = array[i];
        }
        // 找到right
        for (int i = 0; i < len; i++)
        {
            if (array[i] < min)  ret[1] = i;
            else min = array[i];
        }
        return ret;
    }
};

//数据流的中位数
class MedianFinder
{
    priority_queue<int> left; // ⼤根堆
    priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:
    MedianFinder()
    {}
    void addNum(int num)
    {
        // 分类讨论即可
        if (left.size() == right.size()) // 左右两个堆的元素个数相同
        {
            if (left.empty() || num <= left.top()) // 放 left ⾥⾯
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if (num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }
    }
    double findMedian()
    {
        if (left.size() == right.size()) return (left.top() + right.top()) /
            2.0;
        else return left.top();
    }
};

// BFS - 图像渲染
class Solution
{
    typedef pair<int, int> PII;
    // 一个元素的上下左右元素的位置
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        // 先标记一下需要修改的像素值
        int prev = image[sr][sc];
        // 若需要修改的元素值与 修改后的元素值相同，则直接返回
        if (prev == color)   return image;

        int m = image.size();   // 行
        int n = image[0].size();// 列

        queue<PII> q;
        q.push({ sr, sc });   // 让第一个元素入队列

        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();
            // 将该位置的像素值 改为 指定像素值
            image[ret.first][ret.second] = color;
            for (int i = 0; i < 4; i++)
            {
                // 上下左右元素的位置
                int x = ret.first + dx[i], y = ret.second + dy[i];
                // 保证数组不越界，且上下左右的元素 等于 需要修改的像素值
                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
                {
                    q.push({ x, y });
                }
            }
        }
        return image;
    }
};

// BFS - 岛屿数量
class Solution
{
    // 定义方向数组
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    bool vis[301][301];
    int m, n;
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // 遍历grid 
                if (grid[i][j] == '1' && vis[i][j] == false)
                {
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({ i, j });
        vis[i][j] = true;

        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();

            for (int k = 0; k < 4; k++)
            {
                // [x][y]为当前元素的上下左右元素
                int x = ret.first + dx[k], y = ret.second + dy[k];
                // 判断上下左右元素符不符合要求
                if (x >= 0 && x < m && y >= 0 && y < n &&
                    vis[x][y] == false && grid[x][y] == grid[i][j])
                {
                    q.push({ x, y });
                    vis[x][y] = true;
                }
            }
        }
    }
};
// BFS - 岛屿的最⼤⾯积
class Solution
{
    // 位置数组
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    bool vis[51][51];
    int m, n;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        // 遍历grid数组
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // 符合条件就 进入bfs函数
                if (grid[i][j] == 1 && vis[i][j] == false)
                {
                    // 统计面积的较大值
                    ret = max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({ i,j });
        vis[i][j] = true;
        int cnt = 1; //只要进入bfs函数 说明就有一块面积

        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = ret.first + dx[k], y = ret.second + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n &&
                    vis[x][y] == false && grid[x][y] == grid[i][j])
                {
                    q.push({ x, y });
                    cnt++;  // 统计岛屿面积
                    vis[x][y] = true;
                }
            }
        }
        return cnt;
    }
};

// BFS - 被围绕的区域
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int m, n;
public:
    void solve(vector<vector<char>>& board)
    {
        m = board.size(), n = board[0].size();
        // 1.先处理边缘为'O'的连通块，将之修改为'?'
        //  第一行和最后一行
        for (int i = 0; i < n; i++)
        {
            if (board[0][i] == 'O')  bfs(board, 0, i);
            if (board[m - 1][i] == 'O')  bfs(board, m - 1, i);
        }
        //  第一列和最后一列
        for (int j = 0; j < m; j++)
        {
            if (board[j][0] == 'O')  bfs(board, j, 0);
            if (board[j][n - 1] == 'O')  bfs(board, j, n - 1);
        }
        // 2.还原
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == 'O')  board[i][j] = 'X';
                else if (board[i][j] == '?')   board[i][j] = 'O';
            }
        }
    }
    void bfs(vector<vector<char>>& board, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({ i, j });
        // 进入到bfs函数 说明该位置的元素是'O'，将之修改为指定的字符
        board[i][j] = '?';

        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();

            for (int k = 0; k < 4; k++)
            {
                // 当前位置的 上下左右元素
                int x = ret.first + dx[k], y = ret.second + dy[k];
                // 判断是否符合修改条件
                if (x >= 0 && x < m && y >= 0 && y < n &&
                    board[x][y] == 'O')
                {
                    board[x][y] = '?';
                    q.push({ x, y });
                }
            }
        }
    }
};
// BFS - 最短路径问题_迷宫中离⼊⼝最近的出⼝
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    bool vis[101][101]; // 辅助数组
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
    {
        int m = maze.size(), n = maze[0].size();
        queue<pair<int, int>> q;
        // 将小人位置入队列，并将该位置置为true
        q.push({ entrance[0], entrance[1] });
        vis[entrance[0]][entrance[1]] = true;
        int lev = 0;// 记录走了多少步(层序遍历的层数)
        while (!q.empty())
        {
            lev++;  
            int size = q.size();
            // 每次让队列中的元素全部出队列，并将与之相连的元素进队列
            for (int z = 0; z < size; z++)
            {
                auto ret = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    // 判断当前元素的上下左右元素是否满足条件
                    int x = ret.first + dx[k], y = ret.second + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n &&
                        vis[x][y] == false && maze[x][y] == '.')
                    {
                        // 判断是否走到了矩阵的边缘部分
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1)    return lev;
                        q.push({ x, y }); // 将元素入队列
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};
// 堆--前K个高频单词
class Solution
{
    struct Compare
    {
        // 仿函数 让其按照 pair的第二个参数比较
        bool operator()(pair<int, int>& x, pair<int, int>& y)
        {
            return x.second > y.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (auto& e : nums)
            hash[e]++;  // 统计每个元素的个数

        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> heap;
        // 写法一
        for (auto& e : hash)
        {
            if (heap.size() == k)
            {
                if (heap.top().second < e.second)
                {
                    heap.pop();
                    heap.push({ e.first, e.second });
                    // heap.emplace(e.first, e.second);    // 等价于上面一行
                }
            }
            else    heap.push({ e.first, e.second });
        }
        // 写法二
        // for(auto& [num, cnt] : hash)
        // {
        //     if(heap.size() == k)
        //     {
        //         if(heap.top().second < cnt)
        //         {
        //             heap.pop();
        //             heap.push({num, cnt});
        //         }
        //     }
        //     else    heap.push({num, cnt});
        // }
        vector<int> v;
        while (!heap.empty())
        {
            // 优先级队列里面没有front()函数，只有top()函数
            v.push_back(heap.top().first);
            heap.pop();
        }
        return v;
    }
};

#include <unordered_set>
// 最⼩基因变化 - BFS(多看几遍)
class Solution
{
public:
    int minMutation(string startGene, string endGene, vector<string>& bank)
    {
        unordered_set<string> vis;  // ⽤来标记已经搜索过的状态
        unordered_set<string> hash(bank.begin(), bank.end());   // 存储基因库里面的字符串

        string str = "ACGT";// 每个字符可能取的值

        // 若一开始 起始基因 就与 结束基因相同，则直接返回0
        if (startGene == endGene)    return 0;
        // 若基因库中没有 结束基因 ，就说明怎么变化也不会得到结束基因
        if (!hash.count(endGene))  return -1;

        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);  // 将入队列的元素做标记
        int cnt = 0;

        while (!q.empty())
        {
            cnt++;
            int size = q.size();
            while (size--)
            {
                string ret = q.front();
                q.pop();
                for (int i = 0; i < 8; i++)
                {
                    string tmp = ret;   // 不能直接修改ret，不然会导致需改两次的问题
                    for (int j = 0; j < 4; j++)
                    {
                        tmp[i] = str[j];
                        // 若修改后的string存在于基因库中，且没有被标记，则入队列
                        if (hash.count(tmp) && !vis.count(tmp))
                        {
                            // 判断变化后的string是否已经与目标string相同，若相同则直接返回
                            if (tmp == endGene)  return cnt;

                            q.push(tmp);
                            vis.insert(tmp);    // 标记
                        }
                    }
                }
            }
        }
        return -1;
    }
};
// BFS - 单词接龙(与上题一样)
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        unordered_set<string> vis;  // 标记已经搜索过的单词
        unordered_set<string> hash(wordList.begin(), wordList.end());
        string str = "abcdefghijklmnopqrstuvwxyz";
        //for(char ch = 'a'; ch <= 'z'; ch++)

        if (beginWord == endWord)    return 2;
        if (!hash.count(endWord))    return 0;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int cnt = 0;
        while (!q.empty())
        {
            cnt++;
            int size = q.size();
            while (size--)
            {
                string ret = q.front();
                q.pop();

                for (int i = 0; i < ret.size(); i++)
                {
                    string tmp = ret;
                    for (int j = 0; j < 26; j++)
                    {
                        tmp[i] = str[j];
                        if (hash.count(tmp) && !vis.count(tmp))
                        {
                            if (tmp == endWord)  return cnt + 1;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};
// 多源 BFS  - 矩阵
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        int m = mat.size(), n = mat[0].size();
        // dist[i][j] == -1 表⽰：没有搜索过
        // dist[i][j] != -1 表⽰：最短距离
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        // 1. 把所有的源点加⼊到队列中
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == 0)
                {
                    q.push({ i, j });
                    dist[i][j] = 0;
                }
        // 2. ⼀层⼀层的往外扩
        while (!q.empty())
        {
            auto ret = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = ret.first + dx[i], y = ret.second + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[ret.first][ret.second] + 1;
                    q.push({ x, y });
                }
            }
        }
        return dist;
    }
};

// 多源BFS - ⻜地的数量
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    int numEnclaves(vector<vector<int>>& grid)
    {
        // 正难则反
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n));
        queue<pair<int, int>> q;

        // 把四周的1加入队列
        // 第一行和最后一行
        for (int i = 0; i < n; i++)
        {
            if (grid[0][i] == 1)
            {
                q.push({ 0, i });
                vis[0][i] = true;
            }
            if (grid[m - 1][i] == 1)
            {
                q.push({ m - 1, i });
                vis[m - 1][i] = true;
            }
        }
        // 第一列和最后一列
        for (int i = 0; i < m; i++)
        {
            if (grid[i][0] == 1)
            {
                q.push({ i, 0 });
                vis[i][0] = true;
            }
            if (grid[i][n - 1] == 1)
            {
                q.push({ i, n - 1 });
                vis[i][n - 1] = true;
            }
        }
        // 多源BFS
        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = ret.first + dx[k], y = ret.second + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n
                    && vis[x][y] == false && grid[x][y] == 1)
                {
                    vis[x][y] = true;
                    q.push({ x, y });
                }
            }
        }
        int cnt = 0;
        // 统计结果
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && vis[i][j] == false) cnt++;
            }
        }
        return cnt;
    }
};

// 多元BFS - 地图中的最⾼点
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
    {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> vis(m, vector<int>(n, -1));
        queue<pair<int, int>> q;

        // 将所有的源点加入队列
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (isWater[i][j] == 1)
                {
                    // 将水域格子都置为0，并把该位置加入队列
                    vis[i][j] = 0;
                    q.push({ i, j });
                }
            }
        }
        // 多元BFS
        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = ret.first + dx[k], y = ret.second + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n
                    && vis[x][y] == -1 && isWater[x][y] == 0)
                {
                    // 一层一层往外扩， 每阔一层就加一
                    vis[x][y] = vis[ret.first][ret.second] + 1;
                    q.push({ x, y });
                }
            }
        }
        return vis;
    }
};
// BFS - 地图分析
class Solution
{
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
public:
    int maxDistance(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        // 将所有的源点加入队列
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1)
                {
                    vis[i][j] = 0;
                    q.push({ i, j });
                }
        // 多元BFS
        while (!q.empty())
        {
            auto ret = q.front();
            q.pop();

            for (int k = 0; k < 4; k++)
            {
                int x = ret.first + dx[k], y = ret.second + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < n
                    && vis[x][y] == -1 && grid[x][y] == 0)
                {
                    vis[x][y] = vis[ret.first][ret.second] + 1;
                    q.push({ x, y });
                }
            }
        }
        int ans = -1;
        // 遍历vis寻找最大值
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (vis[i][j] > ans)
                    ans = vis[i][j];
        return ans == 0 ? -1 : ans;
    }
};

// BFS 解决拓扑排序 - 课程表
class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        // 1.准备工作
        unordered_map<int, vector<int>> edges;// 邻接表存图
        vector<int> in(numCourses);//存每个顶点的入度

        // 2. 建图
        for (auto& e : prerequisites)
        {
            int a = e[0], b = e[1]; //b->a
            edges[b].push_back(a); // b连接a，把这条边存入edges
            in[a]++;// 入度++
        }

        // 3.拓扑排序
        queue<int> q;
        // (1)把所有入读为零的点加入到队列
        for (int i = 0; i < numCourses; i++)
        {
            if (in[i] == 0)  q.push(i);
        }

        // (2)BFS
        while (!q.empty())
        {
            int tmp = q.front(); q.pop();

            // 将所有与tmp相连的点，入度都--
            for (int a : edges[tmp])
            {
                in[a]--;
                if (in[a] == 0)
                    q.push(a);
            }
        }

        // 4.判断是否有环
        for (int a : in)
            if (a != 0)  return false;
        return true;
    }
};

// BFS 解决拓扑排序 - 课程表2
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<vector<int>> edges(numCourses);// 邻接表存图
        vector<int> in(numCourses);// 存储每一个顶点的入度

        // 2.建图
        for (auto& v : prerequisites)
        {
            int a = v[0], b = v[1];//b->a
            edges[b].push_back(a);
            in[a]++;
        }
        // 3.拓扑排序
        queue<int> q;
        vector<int> ret;
        for (int i = 0; i < numCourses; i++)
        {
            if (in[i] == 0)  q.push(i);
        }

        // 4.BFS
        while (!q.empty())
        {
            int tmp = q.front(); q.pop();
            ret.push_back(tmp);
            for (int e : edges[tmp])
            {
                in[e]--;
                if (in[e] == 0)  q.push(e);
            }
        }
        // 5. 判断
        if (ret.size() == numCourses) return ret;
        else return {};
    }
};

// 优选算法完 - 复习